// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏，实际上就是暴搜
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 14：
// 你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。
// 每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
//
//        为了使收益最大化，矿工需要按以下规则来开采黄金：
//
//        每当矿工进入一个单元，就会收集该单元格中的所有黄金。
//        矿工每次可以从当前位置向上下左右四个方向走。
//        每个单元格只能被开采（进入）一次。
//        不得开采（进入）黄金数目为 0 的单元格。
//        矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
//
//
//        示例 1：
//
//        输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
//        输出：24
//        解释：
//        [[0,6,0],
//        [5,8,7],
//        [0,9,0]]
//        一种收集最多黄金的路线是：9 -> 8 -> 7。
//        示例 2：
//
//        输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
//        输出：28
//        解释：
//        [[1,0,7],
//        [2,0,6],
//        [3,4,5],
//        [0,3,0],
//        [9,0,20]]
//        一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
//
//
//        提示：
//
//        1 <= grid.length, grid[i].length <= 15
//        0 <= grid[i][j] <= 100
//        最多 25 个单元格中有黄金。

// 解题思路：
// 仍然是 dfs 暴搜的策略：上下左右搜索 4 个位置
// 搜过一个位置，就标记为 true
// 如果没得走了，收集结果，收集完结果要记得回溯
// 如果有的走就继续走，直到没得走

public class GetMaximumGold {
    int m = 0;
    int n = 0;
    boolean[][] check;
    int ret = 0;
    int path = 0;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int getMaximumGold(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        check = new boolean[m][n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] != 0){
                    check[i][j] = true;
                    path += grid[i][j];
                    dfs(grid, i, j);
                    check[i][j] = false;
                    path -= grid[i][j];
                }
            }
        }
        return ret;
    }

    public void dfs(int[][] grid, int i, int j){
        ret = Math.max(ret, path);

        for(int k = 0; k < 4; k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && grid[x][y] != 0){
                check[x][y] = true;
                path += grid[x][y];
                dfs(grid, x, y);
                check[x][y] = false;
                path -= grid[x][y];
            }
        }
    }
}
